1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to memory management of computer systems using what has come to be known as “garbage collection.”
2. Description of the Related Art
In the field of computer systems, considerable effort has been expended on the task of allocating and managing memory. In general, memory may be allocated to data objects (which may also be referred to as data structures or records) either statically or dynamically. Some computer languages may require that memory be allocated for all the variables defined in a program statically, e.g., at compile time. Such static memory allocation may make it difficult to share available memory space among multiple applications, especially for applications that are long-lived. Abiding by space limitations may be easier when the platform provides support for dynamic memory allocation, e.g., when memory space to be allocated to a given object is determined only at run time.
Dynamic allocation has a number of advantages, among which is that the run-time system is able to adapt allocation to run-time conditions. For example, the programmer can specify that space should be allocated for a given object only in response to a particular run-time condition. The C-language library function malloc( ) is often used for this purpose. Conversely, the programmer can specify conditions under which memory previously allocated to a given object can be reclaimed for reuse. The C-language library function free( ) results in such memory reclamation. Because dynamic allocation provides for memory reuse, it facilitates generation of large or long-lived applications, which over the course of their lifetimes may employ objects whose total memory requirements would greatly exceed the available memory resources if they were bound to memory locations statically.
Particularly for long-lived applications, though, allocation and reclamation of dynamic memory must be performed carefully. If the application fails to reclaim unused memory—or, worse, loses track of the address of a dynamically allocated segment of memory—its memory requirements may grow over time to exceed the system's available memory. This kind of error is known as a “memory leak.” Another kind of error occurs when an application reclaims memory for reuse even though it still maintains a reference to that memory. If the reclaimed memory is reallocated for a different purpose, the application may inadvertently manipulate the same memory in multiple inconsistent ways. This kind of error is known as a “dangling reference.”
A way of reducing the likelihood of such leaks and related errors is to provide memory-space reclamation in a more automatic manner. Techniques used by systems that reclaim memory space automatically are commonly referred to as garbage collection. Garbage collectors operate by reclaiming space that they no longer consider “reachable.” Statically allocated objects represented by a program's global variables are normally considered reachable throughout a program's life. Such objects are not ordinarily stored in the garbage collector's managed memory space, but they may contain references to dynamically allocated objects that are, and such objects are considered reachable. Clearly, an object referred to in the processor's call stack is reachable, as is an object referred to by register contents. And an object referred to by any reachable object is also reachable. As used herein, a call stack is a data structure corresponding to a process or thread (e.g., of an application), whereby the call stack comprises a sequence of frames that store state information, such as register contents and program counter values, associated with nested routines within the process or thread.
The use of garbage collectors is advantageous because, whereas a programmer working on a particular sequence of code can perform his task creditably in most respects with only local knowledge of the application at any given time, memory allocation and reclamation require a global knowledge of the program. Specifically, a programmer dealing with a given sequence of code does tend to know whether some portion of memory is still in use for that sequence of code, but it is considerably more difficult for him to know what the rest of the application is doing with that memory. By tracing references from some conservative notion of a root set, e.g., global variables, registers, and the call stack, automatic garbage collectors obtain global knowledge in a methodical way. By using a garbage collector, the programmer is relieved of the need to worry about the application's global state and can concentrate on local-state issues, which are more manageable. The result is applications that are more robust, having no dangling references and fewer memory leaks.
Garbage collection mechanisms can be implemented by various parts and levels of a computing system. One approach is simply to provide them as part of a batch compiler's output. In this approach to garbage collection, in addition to generating code for the functionality supported by an application, the batch compiler may generate code that automatically reclaims unreachable memory space without explicit direction from a the programmer, and include it within the application's object code. Even in this simple case, though, there is a sense in which the application does not itself provide the entire garbage collector. Specifically, the application will typically call upon the underlying operating system's memory-allocation functions. And the operating system may in turn take advantage of various hardware that lends itself particularly to use in garbage collection. So even a very simple system may disperse the garbage collection mechanism over a number of computer system layers.
Another approach to garbage collection may be taken in some systems that employ “virtual machines”. In such a system, a compiler or an interpreter may convert source code for an application from a high-level language to instructions called “byte code” for virtual machines that various processors can be configured to emulate. One example of a high-level language for which compilers and interpreters are available to produce such virtual-machine instructions is the Java™ programming language. (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Typically, byte-code routines are executed by a processor under control of a virtual-machine process, and the virtual machine process provides memory management functions including garbage collection. For example, a memory management component of the virtual machine process may be responsible for allocating memory dynamically as needed and reclaiming unreachable memory when possible. Various other approaches to garbage collection may be employed, including implementation of garbage collection functions in hardware.
While an implementation of automatic garbage collection can greatly reduce the occurrence of memory leaks and other software deficiencies, it can also have significant adverse performance effects if it is not implemented carefully. To distinguish the part of the program that does “useful” work from that which does the garbage collection, the term mutator is sometimes used for the “useful” part; from the collector's point of view, what the mutator does is mutate active data structures' connectivity. The instructions executed by the garbage collector are typically considered memory management overhead, and a variety of garbage collection techniques (such as various types of incremental garbage collection, generational garbage collection, etc.) have been devised to reduce the collection overhead relative to the “useful” work done by the mutator.
Mutator operations may be interleaved with garbage collection operations in a variety of ways—for example, a garbage collector may be periodically or aperiodically activated to perform what is called a garbage collection “cycle”, during which a portion or all of the heap (i.e., the dynamically allocated memory) for a mutator may be examined for unreachable objects, and any unreachable objects found may be reclaimed. After the cycle completes, the garbage collector may be deactivated until the next cycle is triggered, e.g., by a detection that insufficient heap memory remains free, or based on a schedule. The mutator may proceed with its operations concurrently with the garbage collection cycle in some implementations, while in other implementations mutator operations may be suspended during at least a part of the garbage collection cycle. Some garbage collectors (which may be termed incremental collectors) may be configured to collect only a subset of the heap at one time.
In distinguishing reachable objects from unreachable objects, garbage collectors often have to trace references between objects—for example, some garbage collectors have to identify those reference fields of an object that have been modified, as well as the objects that are referred to in the modified fields. In order to limit the amount of analysis required for collection, a record or trace of objects whose references have been modified by the mutator may be maintained. In some systems, a sequence of instructions to record such modifications, called a “write barrier”, may be included or inserted into the mutator code for selected write operations of the mutator. Write barrier code may be added to a write operation in the mutator code to record information from which the garbage collector can determine where references were written or may have been written since an earlier collection cycle or collection interval. The information recorded by the write barrier or barriers may be provided to the garbage collector, and may be used by the collector (e.g., during a subsequent collection cycle or interval) to more efficiently identify objects that can be reclaimed. The types of operations performed within a write barrier may vary based on a variety of factors, such as the complexity of the collection algorithm, the data structure or structures used to store the reference tracing information, etc.
The insertion of write barrier code into a mutator code sequence increases the number of instructions executed by the mutator, and thus also tends to increase garbage-collection overhead. A number of different specialized optimization techniques have therefore been proposed to reduce barrier-related overhead. Some techniques check whether a written-to object is dirty and has already been identified as such, and may avoid introducing write barriers into mutator code for such objects. In other techniques, an incremental garbage collector may identify regions of memory that are being collected in a current collection interval or will be collected next, and may be able to skip certain write barrier actions (such as generating remembered set entries for some writes) for such regions. Multi-generational garbage collectors may employ different write barriers for different heap regions or generations, and some garbage collectors may require the application of a sequence of barrier actions for different phases of garbage collection. Multi-threaded collection techniques may also be employed, where, for example, a first set of threads may be configured to identify unreachable objects in a particular region of memory, while a second set of threads may concurrently examine and manipulate or refine memory reference information (e.g., remembered set information) pertaining to other regions that are currently not being collected. Some sophisticated garbage collectors may employ a combination of several of these techniques and/or other techniques that may also employ multiple write barrier actions. It may be difficult to efficiently and flexibly utilize multiple write barrier actions within a single garbage collector using existing techniques—for example, in cases where a collector has multiple phases, and the specific barrier action to use for a particular heap address varies in the different phases. If a complex decision process is used to select an appropriate write barrier action for each write, the processing overhead related to write barriers may become excessive. A more flexible and coarse-grained approach to support the selection of one of multiple possible write barrier actions to be performed for a given write operation (and for determining if any actions are needed at all) may help to simplify garbage collection implementations and further increase the overall efficiency of garbage collection operations.